package day72;

import java.util.*;

public class Solution {
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
          TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        // 栈遍历
//        Stack<TreeNode> stack = new Stack<>();
//        while (root!=null||!stack.isEmpty()) {
//            while (root!=null) {
//                stack.push(root);
//                root = root.left;
//            }
//            root = stack.pop();
//            list.add(root.val);
//            root = root.right;
//        }
//        return list;

        // Morris 遍历
        // 找到前驱节点的最右节点 指向root节点
//        List<Integer> list = new ArrayList<>();
//        TreeNode pre = null;
//
//        while (root!=null) {
//            if(root.left != null) {
//                pre = root.left;
//                while (pre.right!=null && pre.right!=root) {
//                    pre = pre.right;
//                }
//                if(pre.right == null) {
//                    pre.right = root;
//                    root = root.left;
//                } else if(pre.right == root){
//                    list.add(root.val);
//                    pre.right = null;
//                    root = root.right;
//                }
//            } else {
//                list.add(root.val);
//                root = root.right;
//            }
//        }
//        return list;

        List<Integer> ans = new ArrayList<>();
        while (root!=null) {
            if(root.left == null) {
                ans.add(root.val);
                root = root.right;
            } else {
                TreeNode pre = root.left;
                while (pre.right!=null && pre.right!= root) {
                    pre = pre.right;
                }
                if(pre.right == root) {
                    ans.add(root.val);
                    pre.right = null;
                    root = root.right;
                } else {
                    pre.right = root;
                    root = root.left;
                }
            }
        }
        return ans;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
//        Stack<TreeNode> stack1 = new Stack<>();
//        Stack<TreeNode> stack2 = new Stack<>();
//        while (p!=null||!stack1.isEmpty() || q!=null||!stack2.isEmpty()) {
//            while (p!=null) {
//                stack1.push(p);
//                p = p.left;
//            }
//            while (q!=null) {
//                stack2.push(q);
//                q = q.left;
//            }
//            if(stack1.size()!=stack2.size()) return false;
//            p = stack1.pop();
//            q = stack2.pop();
//            if(p.val!=q.val) return false;
//            p = p.right;
//            q = q.right;
//        }
//        return true;
//        if(p == null && q == null) {
//            return true;
//        } else if (p == null) {
//            return false;
//        } else if (q == null) {
//            return false;
//        } else if (p.val!=q.val) {
//            return false;
//        } else {
//            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
//        }

//        if (p == null && q == null) {
//            return true;
//        } else if (p == null || q == null) {
//            return false;
//        }
//        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
//        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
//        queue1.offer(p);
//        queue2.offer(q);
//        while (!queue1.isEmpty() && !queue2.isEmpty()) {
//            TreeNode node1 = queue1.poll();
//            TreeNode node2 = queue2.poll();
//            if (node1.val != node2.val) {
//                return false;
//            }
//            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
//            if (left1 == null ^ left2 == null) {
//                return false;
//            }
//            if (right1 == null ^ right2 == null) {
//                return false;
//            }
//            if (left1 != null) {
//                queue1.offer(left1);
//            }
//            if (right1 != null) {
//                queue1.offer(right1);
//            }
//            if (left2 != null) {
//                queue2.offer(left2);
//            }
//            if (right2 != null) {
//                queue2.offer(right2);
//            }
//        }
//        return queue1.isEmpty() && queue2.isEmpty();

        // Morris 遍历

        while (p!=null && q!=null) {
            if(p.left == null && q.left == null) {
                if(p.val != q.val) {
                    return false;
                }
                p = p.right;
                q = q.right;
            } else if (p.left !=null && q.left != null) {
                TreeNode pre1 = p.left;
                TreeNode pre2 = q.left;
                while (pre1.right!=null && pre1.right!=p) {
                    pre1 = pre1.right;
                }
                while (pre2.right!=null && pre2.right!=q) {
                    pre2 = pre2.right;
                }
                if(pre1.right == null && pre2.right == null) {
                    pre1.right = p;
                    pre2.right = q;
                    p = p.left;
                    q = q.left;
                } else if (pre1.right == p && pre2.right == q) {
                    if(p.val != q.val) {
                        return false;
                    }
                    p = p.right;
                    q = q.right;
                    pre1.right = null;
                    pre2.right = null;
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
        return p==null && q==null;
    }
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }
    private boolean check(TreeNode u,TreeNode v) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if(u == null && v == null) {
                continue;
            }
            if((u == null || v == null) || (u.val != v.val)) {
                return false;
            }
            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
    public int maxDepth(TreeNode root) {
//        if(root == null) return 0;
//        return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            // 全部倒出来
            int t = queue.size();
            while (t>0) {
                if(queue.peek()!=null) {
                    queue.offer(queue.peek().left);
                    queue.offer(queue.peek().right);
                }
                queue.poll();
                t--;
            }
            ans++;
        }
        return ans-1;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums,0,nums.length-1);
    }
    private TreeNode sortedArrayToBST(int[] nums,int l,int r) {
        if(l > r) {
            return null;
        }
        int mid = (l+r)/2;
        TreeNode ans = new TreeNode(nums[mid]);
        ans.left = sortedArrayToBST(nums,l,mid-1);
        ans.right = sortedArrayToBST(nums,mid+1,r);
        return ans;
    }
    public boolean isBalanced(TreeNode root) {
        // 每个节点的最大深度是一样的
        if(root == null) return true;
        if(Math.abs(getHieght(root.left)-getHieght(root.right)) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
    private int getHieght(TreeNode root) {
        if(root == null) return 0;
        return Math.max(getHieght(root.left),getHieght(root.right))+1;
    }
    public int minDepth(TreeNode root) {
//        if(root == null) return 0;
//        if(root.left !=null && root.right != null) {
//            return 1 + Math.min(minDepth(root.left),minDepth(root.right));
//        }
//        if(root.left == null&& root.right == null) {
//            return 1;
//        }
//        if(root.left == null) {
//            return 1+minDepth(root.right);
//        }
//        return 1+minDepth(root.left);

        // dfs 叶子节点 left == null || right == null
        int ans = 0;
        if(root == null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ans++;
            int t = queue.size();
            while (t>0) {
                if(queue.peek().left == null&&queue.peek().right == null) {
                    return ans;
                }
                if(queue.peek().left != null) {
                    queue.offer(queue.peek().left);
                }
                if(queue.peek().right !=null) {
                    queue.offer(queue.peek().right);
                }
                queue.poll();
                t--;
            }
        }
        return 0;
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        if(root.left == null&&root.right == null) {
            return targetSum == root.val;
        }
        return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
//        if(root == null) return false;
//        Queue<TreeNode> queue = new LinkedList<>();
//        Queue<Integer> queueVal = new LinkedList<>();
//        queue.offer(root);
//        queueVal.offer(root.val);
//        while (!queue.isEmpty()) {
//            if(queue.peek().left == null && queue.peek().right == null) {
//                if (queueVal.peek() == targetSum) return true;
//            }
//            int val = queueVal.peek();
//            if(queue.peek().left !=null) {
//                queue.offer(queue.peek().left);
//                queueVal.offer(queue.peek().left.val + val);
//            }
//            if(queue.peek().right !=null) {
//                queue.offer(queue.peek().right);
//                queueVal.offer(queue.peek().right.val + val);
//            }
//            queue.poll();
//            queueVal.poll();
//        }
//        return false;
//        Queue<TreeNode> q = new LinkedList<>();
//        q.offer(root);
//        while (!q.isEmpty()) {
//            TreeNode p = q.poll();
//            if(p == null) continue;
//            if(p.left == null&&p.right == null) {
//                if(p.val == targetSum) return true;
//            }
//            if(p.left != null) {
//                p.left.val += p.val;
//                q.offer(p.left);
//            }
//            if(p.right != null) {
//                p.right.val += p.val;
//                q.offer(p.right);
//            }
//        }
//        return false;
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        //
//        List<Integer> ans = new ArrayList<>();
//        Stack<TreeNode> stack = new Stack<>();
//        while (root!=null || !stack.isEmpty()) {
//            while (root!=null) {
//                ans.add(root.val);
//                stack.push(root);
//                root = root.left;
//            }
//            root = stack.pop().right;
//        }
//        return ans;

        // Morris 遍历
        List<Integer> ans = new ArrayList<>();
        TreeNode p1 = root,p2 = null;
        while (p1!=null) {
            p2 = p1.left;
            if(p2!=null) {
                while (p2.right!=null && p2.right!=p1) {
                    p2 = p2.right;
                }
                if(p2.right == null) {
                    ans.add(p1.val);
                    p2.right = p1;
                    p1 = p1.left;
                    continue;
                } else {
                    p2.right = null;
                }
            } else {
                ans.add(p1.val);
            }
            p1 = p1.right;
        }
        return ans;
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root!=null || !stack.isEmpty()) {
            while (root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right == null || root.right == pre) {
                ans.add(root.val);
                pre = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return ans;
    }
    public TreeNode invertTree(TreeNode root) {
        // 先反转左子树和右子树
//        if(root == null) return root;
//        invertTree(root.left);
//        invertTree(root.right);
//        // 再交换左子树和右子树
//        TreeNode tmp = root.left;
//        root.left = root.right;
//        root.right = tmp;
//        return root;
        if(root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.peek().left;
            queue.peek().left = queue.peek().right;
            queue.peek().right = tmp;
            if(queue.peek().left !=null) {
                queue.offer(queue.peek().left);
            }
            if(queue.peek().right !=null) {
                queue.offer(queue.peek().right);
            }
            queue.poll();
        }
        return root;
    }
    public List<String> binaryTreePaths(TreeNode root) {
        // 二叉树的广度优先搜索
        List<String> paths = new ArrayList<String>();
        if (root == null) {
            return paths;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<String> pathQueue = new LinkedList<String>();

        nodeQueue.offer(root);
        pathQueue.offer(Integer.toString(root.val));

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            String path = pathQueue.poll();

            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                }

                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                }
            }
        }
        return paths;
    }
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null)return 0;
        int ans = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            if(p.right !=null) {
                if(p.right.left!=null || p.right.right !=null) {
                    queue.offer(p.right);
                }
            }
            if(p.left == null) continue;
            if(p.left.left == null && p.left.right == null) {
                ans += p.left.val;
            } else {
                queue.offer(p.left);
            }
        }
        return ans;
    }
    public int[] findMode(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        int maxCount = 0;
        int count = 0;
        int val = 0;
        while (root != null) {
            // 找到前驱节点的最右子节点
            if(root.left != null) {
                TreeNode pre = root.left;
                while (pre.right !=null && pre.right != root) {
                    pre = pre.right;
                }
                if(pre.right == null) {
                    pre.right = root;
                    root = root.left;
                } else {
                    if(root.val == val) {
                        count++;
                    } else {
                        val = root.val;
                        count = 1;
                    }
                    if(count == maxCount) {
                        ans.add(val);
                    } else if (count > maxCount) {
                        ans.clear();
                        ans.add(val);
                        maxCount = count;
                    }
                    pre.right = null;
                    root = root.right;
                }
            } else {
                if(root.val == val) {
                    count++;
                } else {
                    val = root.val;
                    count = 1;
                }
                if(count == maxCount) {
                    ans.add(val);
                } else if (count > maxCount) {
                    ans.clear();
                    ans.add(val);
                    maxCount = count;
                }
                root = root.right;
            }
        }
        int[] arr = new int[ans.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = ans.get(i);
        }
        return arr;
    }
    public int getMinimumDifference(TreeNode root) {
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode pre = null;
//        int ans = Integer.MAX_VALUE;
//        while (root!=null || !stack.isEmpty()) {
//            while (root!=null) {
//                stack.push(root);
//                root = root.left;
//            }
//            root = stack.pop();
//            if(pre == null) {
//                pre = root;
//            } else {
//                ans = Math.min(ans,root.val - pre.val);
//                pre = root;
//            }
//            root = root.right;
//        }
//        return ans;
        // Morris 遍历
        TreeNode pre = null;
        int ans = Integer.MAX_VALUE;
        while (root!=null){
            if(root.left != null) {
                TreeNode p = root.left;
                while (p.right != null && p.right!= root) {
                    p = p.right;
                }
                if(p.right == null) {
                    p.right = root;
                    root = root.left;
                } else {
                    p.right = null;
                    if(pre == null) {
                        pre = root;
                    } else {
                        ans = Math.min(ans,root.val - pre.val);
                        pre = root;
                    }
                    root = root.right;
                }
            } else {
                if(pre == null) {
                    pre = root;
                } else {
                    ans = Math.min(ans,root.val - pre.val);
                    pre = root;
                }
                root = root.right;
            }
        }
        return ans;
    }
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans-1;
    }
    private int depth(TreeNode cur) {
        if(cur == null) return 0;
        int L = depth(cur.left);
        int R = depth(cur.right);
        ans = Math.max(ans,L+R+1);
        return Math.max(L,R)+1;
    }
    public int maxDepth(Node root) {
//        if(root == null) {
//            return 0;
//        }
//        int ans = 0;
//        for (Node n:root.children) {
//            ans = Math.max(ans,maxDepth(n));
//        }
//        return ans+1;
        if(root == null) return 0;
        Queue<Node> queue = new LinkedList<>();
        int ans = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int t = queue.size();
            while (t > 0) {
                if(queue.peek() != null) {
                    for (Node n: queue.peek().children) {
                        queue.offer(n);
                    }
                }
                queue.poll();
                t--;
            }
            ans++;
        }
        return ans;
    }
    int ans = 0;
    public int findTilt(TreeNode root) {
        getSumDiv(root);
        return ans;
    }
    private int getSumDiv(TreeNode cur) {
        if(cur == null) {
            return 0;
        }
        int lSum = getSumDiv(cur.left) + cur.val;
        int rSum = getSumDiv(cur.right) + cur.val;
        ans += (Math.abs(lSum-rSum));
        return lSum+rSum - cur.val;
    }

//    int ans = 0;
//    public int diameterOfBinaryTree(TreeNode root) {
//        getMax(root);
//        return ans;
//    }
//    private void getMax(TreeNode cur) {
//        if(cur == null) return;
//        ans = Math.max(getH(cur.left)+getH(cur.right),ans);
//        getMax(cur.left);
//        getMax(cur.right);
//    }
//    private int getH(TreeNode cur) {
//        // 获得最大深度
//        // 广度优先搜索
//        int ans = -1;
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(cur);
//        while (!queue.isEmpty()) {
//            int t = queue.size();
//            while (t>0) {
//                if(queue.peek()!=null) {
//                    queue.offer(queue.peek().left);
//                    queue.offer(queue.peek().right);
//                }
//                queue.poll();
//                t--;
//            }
//            ans++;
//        }
//        return ans;
//    }
//    int ans = Integer.MAX_VALUE;
//    TreeNode pre;
//    public int getMinimumDifference(TreeNode root) {
//        dfs(root);
//        return ans;
//    }
//    private void dfs(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        dfs(root.left);
//        if(pre !=null) {
//            ans = Math.min(ans,root.val - pre.val);
//        }
//        pre = root;
//        dfs(root.right);
//    }

//    int base, count, maxCount;
//    List<Integer> answer = new ArrayList<Integer>();
//    public int[] findMode(TreeNode root) {
//        // 二叉搜索树
//        // 出现最多的数
//        dfs(root);
//        int[] ans = new int[answer.size()];
//        for (int i = 0; i < ans.length; i++) {
//            ans[i] = answer.get(i);
//        }
//        return ans;
//    }
//    private void dfs(TreeNode o) {
//        if (o == null) return;
//        dfs(o.left);
//        update(o.val);
//        dfs(o.right);
//    }
//    public void update(int x) {
//        if (x == base) {
//            ++count;
//        } else {
//            count = 1;
//            base = x;
//        }
//        if (count == maxCount) {
//            answer.add(base);
//        }
//        if (count > maxCount) {
//            maxCount = count;
//            answer.clear();
//            answer.add(base);
//        }
//    }

//    public int sumOfLeftLeaves(TreeNode root) {
//        return help(root,root.left) + help(root,root.right);
//    }
//    private int help(TreeNode pre,TreeNode cur) {
//        if(cur == null) return 0;
//        if(cur.left == null && cur.right == null) {
//            if(cur == pre.left) {
//                return cur.val;
//            } else {
//                return 0;
//            }
//        }
//        return help(cur,cur.left) + help(cur,cur.right);
//    }
//    public List<String> binaryTreePaths(TreeNode root) {
//        List<String> paths = new ArrayList<String>();
//        constructPaths(root, "", paths);
//        return paths;
//    }
//    public void constructPaths(TreeNode root, String path, List<String> paths) {
//        if (root != null) {
//            StringBuffer pathSB = new StringBuffer(path);
//            pathSB.append(Integer.toString(root.val));
//            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
//                paths.add(pathSB.toString());  // 把路径加入到答案中
//            } else {
//                pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
//                constructPaths(root.left, pathSB.toString(), paths);
//                constructPaths(root.right, pathSB.toString(), paths);
//            }
//        }
//    }

//    public boolean isSymmetric(TreeNode root) {
//        return dfs(root.left,root.right);
//    }
//    private boolean dfs(TreeNode l,TreeNode r) {
//        if(l == null && r == null) return true;
//        if(l == null) return false;
//        if(r == null) return false;
//        if(l.val != r.val) {
//            return false;
//        }
//        boolean ans = dfs(l.left,r.right)&&dfs(l.right,r.left);
//        return ans;
//    }
}
